import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
* @description: 768. 最多能完成排序的块 II
* @author hewei
* @date 2022/8/13 16:15
* @version 1.0
*/

public class MaxChunksToSorted2 {

    public static void main(String[] args) {

    }

    public int maxChunksToSorted1(int[] arr) {
        int n = arr.length;
        Integer[] temp = new Integer[n];
        for (int i = 0; i < n; i++) {
            temp[i] = i;
        }
        Arrays.sort(temp, (a, b) -> {
            if (arr[a] == arr[b]) return a - b;
            return arr[a] - arr[b];
        });
        int i = 0;
        int ans = 0;
        while (i < n) {
            int index = temp[i];
            ++i;
            while (i <= index) {
                if (temp[i] > index) index = temp[i];
                ++i;
            }
            ++ans;
        }
        return ans;
    }

    public int maxChunksToSorted(int[] arr) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i : arr) {
            if (!stack.isEmpty() && stack.peek() > i) {
                Integer poll = stack.poll();
                while (!stack.isEmpty() && stack.peek() > i) stack.poll();
                stack.push(poll);
            } else stack.push(i);
        }
        return stack.size();
    }
}
